package _02_链表;

public class _86_分隔链表 {

    public ListNode partition(ListNode head, int x) {
        if (head == null) return null;
        ListNode left = new ListNode(0);
        ListNode leftTail = left;

        ListNode right = new ListNode(0);
        ListNode rightTail = right;

        while (head != null) {
            if (head.val < x) {
                leftTail = leftTail.next = head;
            } else {
                rightTail = rightTail.next = head;
            }
            head = head.next;
        }
        // 拼接
        rightTail.next = null;
        leftTail.next = right.next;
        return left.next;
    }

}
